package com.yangli.csnote.other;

/**
 * TODO
 *
 * @Author liyang
 * @Date 2022/10/14 11:46
 */
public class Array {
    public static void main(String[] args){
        int[][] data = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        System.out.println(Find(5, data));
    }

    /*
     * 数组中重复的数字
     * 在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
     * */
    public int duplicate(int[] nums){

        //i表示索引位置 num[0] 索引位置上的值
        for (int i = 0; i < nums.length; i++) {
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }
                swap(nums, i, nums[i]);
            }
            swap(nums, i, nums[i]);
        }
        return -1;
    }

    public void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    /**
     * 4. 二维数组中的查找
     * 给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。
     */

    public static boolean Find(int target, int[][] array){
       /* int m = array.length;
        if (m == 0) {
            return false;
        }
        int n = array[0].length;
        if (n == 0) {
            return false;
        }
        if (target < array[0][0] || target > array[m - 1][n - 1]) {
            return false;
        }
        int i = 0, j = 0;
        while (target > array[i][0] && i < m) {
            i++;
        }
        while (target > array[0][j] && j < n) {
            i++;
        }
        for (int i = 0, j = 0; i < m && j < n; ) {
            if (array[i][j] == target) return true;
            if (target > array[i][j] && i < m - 1) {
                i++;
                continue;
            }
            if (target > array[i][j] && j < n - 1) {
                j++;
                continue;
            }
            if (array[i][j] > target && i == m - 1) {
                i = 0;
                continue;
            }

            if (array[i][j] > target && j == n - 1) {
                j = 0;
                continue;
            }
            return false;
        }*/
        return false;

    }

}
